درسنامه آموزشی فصل سوم ریاضیات گسسته کلاس دوازدهم ریاضی
درس 2: روشهایی برای شمارش
اصل شمول و عدم شمول
واضح است که برای محاسبهٔ تعداد اعضای $(A\bigcup B)$ یعنی $\left| A\bigcup B \right|$ چون اعضای $(A\bigcap B)$ هم در A و هم در B هستند، اگر اعضای A و B را روی هم حساب کنیم اعضای $(A\bigcap B)$ دوبار محاسبه شدهاند و میبایست یکبار از این مجموع کم شود و لذا خواهیم داشت:
$\left| A\bigcup B \right|=\left| A \right|+\left| B \right|-\left| A\bigcap B \right|$
این تساوی به اصل شمول و عدم شمول برای دو مجموعه معروف است. (برای اختصار آن را اصل شمول مینامیم).
با توجه به تعریف متمم اگر S مجموعهٔ مرجع A و B باشد، داریم:
$\left| (A\bigcup B{)}' \right|=\left| \overline{A\bigcup B} \right|=\left| S \right|-\left| A\bigcup B \right|$
این تساوی نتیجهٔ اصل شمول است.
نتیجهٔ مهم: اگر S مجموعهای متناهی و A و B زیرمجموعههای S باشند، در اینصورت تعداد اعضایی از S که در هیچیک از مجموعههای A و B قرار ندارند. برابر است با:
$\left| S \right|-\left| A\bigcup B \right|=\left| S \right|-\left| A \right|-\left| B \right|+\left| A\bigcap B \right|$
مثال: در یک کلاس 25 نفری 15 نفر فوتبال و 14 نفر والیبال بازی میکنند. مشخص کنید چند نفر نه فوتبال بازی میکنند و نه والیبال، به شرط آنکه بدانیم 9 نفر هم فوتبال و هم والیبال بازی میکنند.
حل: ابتدا با استفاده از اصل شمول تعداد افرادی را که حداقل در یکی از دو رشتهٔ ورزشی بازی میکنند مشخص میکنیم و سپس با استفاده از نتیجهٔ اصل شمول تعداد افرادی را که در هیچ رشته ورزشی شرکت ندارند بهدست میآوریم.
اگر مجموعهٔ افرادی را که فوتبال و والیبال بازی میکنند بهترتیب F و V بنامیم در اینصورت خواهیم داشت:
$\left| F\bigcup V \right|=\left| F \right|+....-................\Rightarrow \left| F\bigcup V \right|=....$
$=\left| \overline{F\bigcup V} \right|=\left| S \right|-\left| F\bigcup V \right|=25-....=....$ تعداد افرادی که نه در F و نه در V هستند
اصل شمول را میتوان برای بیش از دو مجموعه هم تعمیم داده و بیان کرد که ما در این کتاب برای حداکثر سه مجموعه آن را بیان و مسائلی را با استفاده از این اصل طرح و حل خواهیم کرد.
اصل شمول برای سه مجموعه: اگر B ،A و C زیرمجموعههایی از مجموعهٔ مرجع S باشند، در اینصورت همواره تساوی زیر (اصل شمول) برقرار است:
$\left| A\bigcup B\bigcup C \right|=\left| A \right|+\left| B \right|+\left| C \right|-\left| A\bigcap B \right|-\left| A\bigcap C \right|-\left| B\bigcap C \right|+\left| A\bigcap B\bigcap C \right|$
(توضیح دهید چرا اشتراکهای دوتایی کم و اشتراک سهتایی اضافه شده است؟)
با استفاده از تعریف متمم، نتیجهٔ اصل شمول نیز به صورت زیر بیان میشود:
(تعداد اعضایی از S که در هیچیک از $\left| \overline{A\bigcup B\bigcup C} \right|=\left| S \right|-\left| A\bigcup B\bigcup C \right|$ مجموعههای B ،A و C قرار ندارند)
فعالیت (صفحهٔ 74 تا 75 کتاب درسی)
چند عدد طبیعی مانند n، بهطوریکه $1\le n\le 400$ ، وجود دارد که بر هیچیک از اعداد 3، 4 و 5 بخشپذیر نباشند؟ (بر 3 بخشپذیر نباشند، بر 4 بخشپذیر نبوده و بر 5 نیز بخشپذیر نباشند).
1- در بین اعداد 12، 25، 10 و 13 کدامیک مورد نظر میباشند؟
2- آیا عدد 60 جزء اعداد مورد نظر است؟
3- اگر مجموعهٔ اعدادی را که بر 3 بخشپذیرند A و اعداد بخشپذیر بر 4 را B و اعداد بخشپذیر بر 5 را C بنامیم، $\overline{A}$، $\overline{B}$ و $\overline{C}$ را تعریف کنید. آیا مجموعهٔ $(\overline{A}\bigcap \overline{B}\bigcap \overline{C})$ همهٔ اعداد مورد نظر را شامل میشود؟
4- آیا تساوی $(\overline{A}\bigcap \overline{B}\bigcap \overline{C})=(\overline{A\bigcup B\bigcup C})$ برقرار است؟
5- با توجه به تساوی اخیر و اصل شمول و نتیجهٔ اصل شمول جاهای خالی را پر کرده و تعداد اعداد خواسته شده را محاسبه کنید. (منظور از $\left[ \, \right]$ جزء صحیح است).
$A=\left\{ 1\le n\le 400\left| 3| \right.n \right\}\to \left| A \right|=\left[ \frac{400}{3} \right]=....$
(از هر سه عدد متوالی یکی بر 3 بخشپذیر است، پس تعداد اعداد طبیعی از 1 تا k که بر سه بخشپذیرند برابر است با $\left[ \frac{k}{3} \right]$).
$B=\left\{ 1\le n\le 400\left| ....|n \right. \right\}\to \left| B \right|=\left[ \frac{....}{....} \right]=....$
$C=\left\{ 1\le n\le 400\left| ....|n \right. \right\}\to \left| C \right|=\left[ \frac{....}{....} \right]=....$
$(A\bigcap B)$ یعنی مجموعهٔ اعدادی که هم بر 3 و هم بر 4 بخشپذیرند و با توجه به قضیهای در نظریه اعداد، «مجموعهٔ اعدادی که بر a و بر b بخشپذیر باشد با مجموعهٔ اعدادی که بر «کمم» آن دو عدد یعنی بر $\left[ a,b \right]$ بخشپذیرند، برابر میباشد». (این قضیه برای سه عدد یا بیشتر نیز برقرار است)
$\left| A\bigcap B \right|=\left[ \frac{400}{\left[ 3,4 \right]} \right]=\left[ \frac{400}{12} \right]=....$
$\left| A\bigcap C \right|=\left[ \frac{400}{....} \right]=\left[ \frac{400}{15} \right]=....$
$\left| B\bigcap C \right|=\left[ \frac{....}{....} \right]=\left[ \frac{....}{20} \right]=....$
$\left| A\bigcap B\bigcap C \right|=\left[ \frac{400}{60} \right]=....(\left[ 3,4,5 \right]=\left[ \left[ 3,4 \right],5 \right]=\left[ 12,5 \right]=60)$
$\left| \overline{A}\bigcap \overline{B}\bigcap \overline{C} \right|=\left| \overline{A\bigcup B\bigcup C} \right|=\left| S \right|-\left| A\bigcup B\bigcup C \right|$
$=400-(\left| A \right|+\left| B \right|+\left| C \right|-\left| A\bigcap B \right|-\left| A\bigcap C \right|-\left| B\bigcap C \right|+\left| A\bigcap B\bigcap C \right|)$
$=400-(133+....+....-....-33-....-20+60)=....$
کار در کلاس (صفحهٔ 75 کتاب درسی)
چند عدد طبیعی مانند n، بهطوریکه $1\le n\le 350$، وجود دارد که بر هیچیک از اعداد 4، 5 و 6 بخشپذیر نباشند؟
(توجه داشته باشید که $\left[ 5,6 \right]=30$ و $\left[ 4,6 \right]=12$ و $\left[ 5,4,6 \right]=60$)
مثال: اگر یک قفل رمز دار شامل 4 رقم از صفر تا 9 باشد و بدانیم که رمز بسته شده روی قفل حداقل یک رقم 7 و یک رقم 8 را شامل میشود و امتحان کردن هر رمز 4 رقمی 5 ثانیه طول بکشد حداکثر چه زمانی لازم است تا این قفل باز شود؟ (در رمز، قرار گرفتن رقم صفر در سمت چپ اشکالی ندارد) (این مسئله معادل است با شمارش تعداد 4 رقمیهایی که در هر یک از آنها هر یک از ارقام 7 و 8 وجود داشته باشد.)
حل: یک رمز 4 رقمی را بهصورت $\overline{abcd}$ نمایش میدهیم که در آن c ،b ،a و d ارقام صفر تا 9 میباشند.
محاسبهٔ تعداد چنین ارقامی بهصورت مستقیم کاری وقتگیر است و امکان دارد رمزهایی را چندبار محاسبه کنیم یا رمزهایی را از قلم بیندازیم، لذا از اصل شمول استفاده میکنیم.
ابتدا مجموعههای A و B را بهصورت زیر و مخالف با آنچه مورد نظر مسئله است تعریف میکنیم!
$A=\left\{ \overline{abcd}|a,b,c,d\ne 7 \right\}\to \left| A \right|=9\times 9\times 9\times 9$
$B=\left\{ \overline{abcd}|a,b,c,d\ne .... \right\}\to \left| B \right|=9\times 9\times 9\times 9$
$(A\bigcap B)=\left\{ \overline{abcd}|a,b,c,d\ne 7,8 \right\}\to \left| A\bigcap B \right|=8\times 8\times 8\times 8$
واضح است که منظور از $\overline{A}$ مجموعهٔ اعداد 4 رقمی است که در هر یک از آنها رقم 7 بهکار رفته است و منظور از $\overline{B}$ اعداد 4 رقمی است که در آنها عدد 8 بهکار رفته است. البته $(\overline{A}\bigcap \overline{B})$ یعنی مجموعهٔ اعداد 4 رقمی که در آنها هم رقم 7 و هم رقم 8 بهکار رفته است و تعداد اعضای این مجموعه پاسخ سؤال مطرح شده است.
$=\left| S \right|=10\times 10\times 10\times 10=10000$ تعداد کل 4 رقمیها $\to $ 10 (رقم اول) 10 (رقم دوم) 10 (رقم سوم) 10 (رقم چهارم)
$\left| \overline{A}\bigcap \overline{B} \right|=\left| \overline{A\bigcup B} \right|=\left| S \right|-\left| A\bigcup B \right|$
$=10000-({{9}^{4}}+{{9}^{4}}-{{8}^{4}})=....$
$=....\times 5=....$ زمان لازم برحسب ثانیه
کار در کلاس (صفحهٔ 76 کتاب درسی)
در استان مرکزی، در نزدیکی شهر محلات، سه روستای خورهه، آبگرم و حاجی آباد وجود دارد. اگر بخواهیم جادههایی بین این سه روستا طراحی کنیم، بهطوریکه پس از تکمیل راهها، هیچ روستایی تنها نماند (حداقل به یک روستای دیگر وصل باشد) به چند طریق میتوان چنین راههایی را طراحی کرد؟
اگر روستاها را A ،K و H بنامیم، در اینصورت یافتن تعداد چنین راههایی معادل است با پیدا کردن تعدادی گرافهای ساده که با سه رأس A ،K و H میتوان تعریف کرد بهطوریکه در آنها هیچ رأسی تنها نباشد.
1- از چهار گراف سادهٔ زیر کدامها مورد نظرند و کدامها را نباید شمرد؟
2- کل جادههای بین سه روستا یعنی کل گرافهای ممکن که با سه رأس میتوان تعریف کرد برابر است با:
$\left| S \right|={{2}^{\left( \begin{matrix}
3 \\
2 \\
\end{matrix} \right)}}=....$
(بین هر دو روستا از این سه روستا میتوان یک جاده در نظر گرفت که هر جاده میتواند در طراحیِ ما، باشد یا نباشد).
3- اگر ${{A}_{k}}$ را مجموعهٔ راههای طراحی شدهای که در آنها روستای K تنها بماند تعریف کنیم، به همین صورت ${{A}_{a}}$ و ${{A}_{h}}$ را تعریف کنید و با استفاده از نتیجهٔ اصل شمول جواب را بیابید و گرافهای متناظر با آنها را رسم کنید.
4- توضیح دهید که چرا تساویهای زیر برقرارند؟
$\left| {{A}_{k}} \right|=\left| {{A}_{a}} \right|=\left| {{A}_{h}} \right|=2$ (الف
$\left| {{A}_{k}}\bigcap {{A}_{a}} \right|=\left| {{A}_{k}}\bigcap {{A}_{h}} \right|=\left| {{A}_{a}}\bigcap {{A}_{h}} \right|=1$ (ب
$\left| {{A}_{k}}\bigcap {{A}_{a}}\bigcap {{A}_{h}} \right| = 1$ (پ
فعالیت (صفحهٔ 77 کتاب درسی)
اگر f تابعی از مجموعهٔ A به مجموعهٔ B باشد و $\left| A \right|=m$ و $\left| B \right|=n$، در اینصورت برای هر ${{a}_{i}}\in A$ که $1\le i\le m$ میتوان به n طریق $f({{a}_{i}})$ را تعریف کرد.
$f({{a}_{i}})={{b}_{1}}$ یا $f({{a}_{i}})={{b}_{2}}$ ..... یا $f({{a}_{i}})={{b}_{n}}$ و لذا طبق اصل ضرب تعداد کل توابع از A به B برابر است با: ${{\left| B \right|}^{\left| A \right|}}={{n}^{m}}$. حال اگر $\left| A \right|=5$ و $\left| B \right|=3$، در اینصورت میخواهیم تعداد توابعی چون f از A به B را تعیین کنیم بهطوریکه ${{R}_{f}}=B$. (روی تمام اعضای B، پیکانی رسم شده باشد، به چنین تابعهایی، تابع پوشا گفته میشود.)
1- اگر فرض کنیم $B=\left\{ {{b}_{1}},{{b}_{2}},{{b}_{3}} \right\}$ و $A=\left\{ {{a}_{1}},{{a}_{2}},{{a}_{3}},{{a}_{4}},{{a}_{5}} \right\}$ و تعریف کنیم،
${{A}_{1}}=\left\{ f:A\to B\left| f({{a}_{i}})\ne {{b}_{1}};1\le i\le 5 \right. \right\}$
${{A}_{2}}=\left\{ f:A\to B\left| f({{a}_{i}})\ne ....;1\le i\le 5 \right. \right\}$
${{A}_{3}}=\left\{ f:A\to B\left| f({{a}_{i}})\ne ....;1\le i\le 5 \right. \right\}$
در اینصورت ${{\overline{A}}_{1}}$ مجموعهای شامل همه تابعهایی از A به B است که حداقل یک پیکان از اعضای A روی ${{b}_{1}}$ میآورند.
2- مجموعهٔ $(\overline{{{A}_{1}}}\bigcap \overline{{{A}_{2}}}\bigcap \overline{{{A}_{3}}})=(\overline{{{A}_{1}}\bigcap {{A}_{2}}\bigcap {{A}_{3}}})$ را تعریف کنید و با استفاده از نتیجه اصل شمول، پاسخ را بیابید.
$\left| S \right|={{3}^{....}}=....\,,\,\left| {{A}_{1}} \right|=\left| {{A}_{2}} \right|=\left| {{A}_{3}} \right|={{2}^{....}}=....$
$\left| {{A}_{1}}\bigcap {{A}_{2}} \right|=\left| {{A}_{1}}\bigcap {{A}_{3}} \right|=\left| {{A}_{2}}\bigcap {{A}_{2}} \right|=....\,,\,\left| {{A}_{1}}\bigcap {{A}_{2}}\bigcap {{A}_{3}} \right|=0$
$(\overline{{{A}_{1}}\bigcup \left| {{A}_{2}}\bigcup {{A}_{3}} \right.})=\left| S \right|-\left| {{A}_{1}}\bigcup {{A}_{2}}\bigcup {{A}_{3}} \right|$
$=243-(....+....+....-....-....-....+....)=....$
مثال: به چند طریق میتوان 4 خودکار متفاوت را بین سه نفر توزیع کرد به شرط آنکه به هر نفر حداقل 1 خودکار داده باشیم؟
حل: تعداد حالتهای ممکن برای انجام این عمل معادل است با پیدا کردن تعداد تابعهایی از یک مجموعهٔ 4 عضوی مانند A به یک مجموعهٔ 3 عضوی مانند B، بهطوریکه بُرد این توابع همهٔ اعضای B باشد. (به هر عضو B حداقل 1 عضو از A نسبت داده شود.)
${{A}_{j}}=\left\{ f:A\to B\left| f({{a}_{i}})\ne {{b}_{j}}\,,\,1\le i\le 4 \right. \right\},1\le j \le 3$
$\left| S \right|={{\left| B \right|}^{\left| A \right|}}={{3}^{4}}=81$
$\left| {{A}_{1}} \right|=\left| {{A}_{2}} \right|=\left| {{A}_{3}} \right|={{2}^{4}}=16$
$\left| {{A}_{1}}\bigcap {{A}_{2}} \right|=\left| {{A}_{1}}\bigcap {{A}_{3}} \right|=\left| {{A}_{2}}\bigcap {{A}_{3}} \right|={{1}^{4}}=1\,,\,\left| {{A}_{1}}\bigcap {{A}_{2}}\bigcap {{A}_{3}} \right|=0$
$\left| \overline{{{A}_{1}}}\bigcap \overline{{{A}_{2}}}\bigcap \overline{{{A}_{3}}} \right|=\left| \overline{{{A}_{1}}\bigcup {{A}_{2}}\bigcup {{A}_{3}}} \right|=\left| S \right|-\left| {{A}_{1}}\bigcup {{A}_{2}}\bigcup {{A}_{3}} \right|$
$=81-(3\times 16-3\times 1+0)=36$
تذکر: تعداد تابعهایی چون $f:A\to B$ با فرض $\left| A \right|=m\ge 3$ و $\left| B \right|=3$ بهطوریکه ${{R}_{f}}=B$، از رابطهٔ ${{3}^{m}}-(3\times {{2}^{m}}-3)$ بهدست میآید.
مثال: 8 نفر را که برای یک برنامه تلویزیونی پیامک ارسال کردهاند، انتخاب کردهایم و میخواهیم در 4 مرحله و در هر مرحله 1 جایزه را به یکی از این 8 نفر (با قرعهکشی) به دلخواه بدهیم. این عمل به چند طریق امکانپذیر است؟ (یک نفر میتواند 4 جایزه را برنده شود.)
حل: حل این مثال معادل است با یافتن تعداد تابعهای ممکن از یک مجموعهٔ 4 عضوی به یک مجموعهٔ 8 عضوی که برابر است با ${{8}^{4}}=4096$
فعالیت (صفحهٔ 78 کتاب درسی)
میخواهیم تعداد تابعهای یک به یک مجموعهٔ 4 عضوی به یک مجموعهٔ 6 عضوی را شمارش کنیم،
1- اگر فرض کنیم $A=\left\{ {{a}_{1}},{{a}_{2}},{{a}_{3}},{{a}_{4}} \right\}$ و $B=\left\{ {{b}_{1}},{{b}_{2}},...,{{b}_{6}} \right\}$ برای تعریف f روی هر عضو A مثلاً $f({{a}_{1}})$، چند راه انتخاب داریم؟
2- با توجه به اینکه f باید یکبهیک باشد و تعریف یکبهیکی در توابع، پس از تعریف $f({{a}_{1}})$، برای تعریف f روی ${{a}_{2}}$ چند راه انتخاب داریم؟
3- با توجه به اصل ضرب، در کل، چند تابع یکبهیک از A به B میتوان تعریف کرد؟ پاسخ خود را توسط تبدیل r شیء از n شیء بنویسید.
به 6 طریق میتوان $f({{a}_{1}})$ را تعریف کرد ${{b}_{6}}\to $ یا ... یا ${{b}_{2}}$ یا $f({{a}_{1}})={{b}_{1}}$
به 5 طریق میتوان $f({{a}_{2}})$ را تعریف کرد $f\Rightarrow f({{a}_{2}})\ne f({{a}_{1}})\to $ یکبهیک است
$f\Rightarrow f({{a}_{3}})\ne f({{a}_{1}})\,,\,f({{a}_{3}})\ne f({{a}_{2}})\Rightarrow ....$ یکبهیک است
..................................................................................................................
$=6\times 5\times ...\times ...=\frac{6!}{....}={{(6)}_{4}}$ تعداد کل تابعهای یکبه یک $\Rightarrow $ طبق اصل ضرب
در حالت کلی اگر $\left| A \right|=m$ و $\left| B \right|=k$ در اینصورت با شرط $m\le k$ تعداد توابع از مجموعهٔ A به مجموعهٔ B برابر است با تعداد انتخابهای m شیء از بین k شیء یا ${{(k)}_{m}}=\frac{k!}{(k-m)!}$.
مثال: به چند طریق میتوان 4 خودکار متفاوت را بین 8 نفر توزیع کرد به شرط آنکه هیچکس بیشتر از یک خودکار نداشته باشد؟ (به هر نفر حداکثر یک خودکار داده باشیم)
حل: تعداد حالتهای ممکن برای انجام این عمل معادل است با پیدا کردن تعداد تابعهای یکبهیک از مجموعهای 4 عضوی به مجموعهای .... عضوی یعنی،
${{(8)}_{4}}=\frac{....}{....}=....$
اصل لانه کبوتری
اگر از شما سؤال شود که حداقل چند نفر باید در یک کلاس حضور داشته باشند تا مطمئن شوید لااقل دو نفر از آنها ماه تولّدشان یکسان است، چه پاسخی میدهید؟ بدترین حالت ممکن این است که افراد داخل کلاس از نفر اول هر کدام در یک ماه متفاوت با نفر قبلی به دنیا آمده باشند، تا کجا میتوان مقاومت کرد؟ واضح است که حداکثر تا 12 نفر با فرض اینکه هر نفر در یک ماه متفاوت از بقیه متولد شده باشد، میتوان به این روند ادامه داد و هنوز اطمینانی برای اینکه حداقل دو نفر ماه تولدشان مثل هم باشد وجود ندارد، ولی اگر 13 نفر در کلاس حضور داشته باشند این اطمینان حاصل میشود! (نفر سیزدهم در هر ماهی متولد شده باشد، 1 نفر از آن 12 نفر در آن ماه متولد شده است.)
حال با توجه به مطالب فوق به نظر شما حداقل چند دانشآموز در یک مدرسه باید حضور داشته باشند تا اطمینان داشته باشیم، حداقل 2 نفر از آنها روز تولدشان یکی است؟
در این قسمت به بیان اصل لانه کبوتری پرداخته و سپس مسائلی را مطرح میکنیم و با استفاده از این اصل و تعمیم آن، مسائل را حل خواهیم کرد.
اصل لانه کبوتری:
اگر m کبوتر و n لانه داشته باشیم و $m\gt n$ و همهٔ کبوترها درون لانهها قرار بگیرند، در اینصورت لانهای وجود دارد که حداقل 2 کبوتر در آن قرار گرفته است.
مثال: نشان دهید اگر بخواهیم ضلعهای یک مثلث را با دو رنگ آبی یا قرمز رنگ کنیم، حداقل دو ضلع این مثلث همرنگ خواهند شد.
حل: اگر ضلعهای مثلث را کبوترها و دو رنگ آبی و قرمز را لانهها فرض کنیم، طبق اصل لانه کبوتری در یکی از لانهها حداقل 2 کبوتر قرار خواهد گرفت (دو کبوتر در یک لانه معادل است با دو ضلع با یک رنگ).
مثال: ثابت کنید در بین هر 5 عدد طبیعی دلخواه حداقل دو عدد یافت میشود بهطوریکه به پیمانهٔ 4 همنهشت میباشند.
حل: میدانیم باقیماندهٔ تقسیم هر عدد بر 4 یکی از اعضای مجموعهٔ $R=\left\{ 0,1,2,3 \right\}$ است، حال اگر 5 عدد طبیعی را کبوترها و باقیماندههای تقسیم اعداد بر 4 را لانهها فرض کنیم، طبق اصل لانه کبوتری حداقل 2 کبوتر در یک لانه قرار خواهند گرفت، یعنی حداقل دو عدد از این 5 عدد باقیماندههای تقسیمشان بر 4 با هم برابر است. حال اگر آن دو عدد را a و b فرض کنیم، a و b بر 4 هم باقیمانده بوده و بنابر تعریف همنهشتی باید $a\overset{4}{\mathop{\equiv }}\,b$ و حکم بهدست میآید.
تمرین: در حالت کلّی ثابت کنید در بین هر $(n+1)$ عدد طبیعی دلخواه و بیشتر، همواره حداقل 2 عدد مانند a و b یافت میشوند به قسمی که تفاضل آنها بر n بخشپذیر است. (به پیمانهٔ n همنهشتاند).
کار در کلاس (صفحهء 80 کتاب درسی)
1- یک مثلث متساویالاضلاع به طول ضلع 3 واحد را تقسیمبندی کردهایم. نشان دهید اگر 10 نقطه دلخواه از داخل این مثلث اختیار کنیم حداقل 2 نقطه بین این نقاط وجود خواهد داشت به قسمی که فاصلهٔ آنها از یکدیگر کمتر از 1 باشد.
2- با توجه به 1 برای شکل مقابل یک مسئله طرح کنید و با استفاده از اصل لانه کبوتری به آن پاسخ دهید.
3- نشان دهید در یک خانوادهٔ حداقل 5 نفری، دست کم دو نفر فصل تولدشان یکی است.
4- نشان دهید در هر گراف ساده از مرتبهٔ $P\ge 2$ حداقل دو رأس هم درجه وجود دارد. (راهنمایی: مسئله را در دو حالت بررسی کنید.)
(1) حالتی که رأس ایزوله یا تنها نداشته باشیم که در اینصورت درجات رئوس از 1 تا $n-1$ تغییر میکند.
(2) حالتیکه یک رأس تنها داشته باشیم که در اینصورت درجات بقیهٔ رئوس از 1 تا $n-2$ تغییر میکند) آیا نیازی هست حالتی را در نظر بگیریم که دو رأس یا بیشتر تنها باشند؟
جدول زیر را (با توجه به قرار دادن n کبوتر در n لانه در هر مرحله) کامل کنید و نتیجهگیری خود را با نتیجه داخل کادر (تعمیم اصل لانه کبوتری) مقایسه کنید.
| اطمینان از وجود لانهای با حداقل ($k+1$) کبوتر | تعداد کبوترها ($kn+1$) | تعداد لانهها ($n$) |
|---|---|---|
| اطمینان از وجود لانهای با حداقل 2 کبوتر | $1 \times n+1$ | $n$ |
| اطمینان از وجود لانهای با حداقل ....... کبوتر | $2 \times n+1$ | $n$ |
| اطمینان از وجود لانهای با حداقل 4 کبوتر | $.....+1$ | $n$ |
| اطمینان از وجود لانهای با حداقل .......... کبوتر | $.....+1$ | $n$ |
همانطور که مشاهده میکنید در سطر دوم بهازای $n=4$ و $k=2$ تعداد کبوترها $2\times 4+1=9$ میباشد که طبق جدول میبایست لانهای با حداقل 3 کبوتر یافت شود و شکل زیر گویای این روش است که اگر در هر لانه یک کبوتر قرار بگیرد و از هر 5 کبوتر باقیمانده مجدّد در هر لانه 1 کبوتر قرار بگیرد در نهایت نهمین کبوتر در هر لانهای قرار بگیرد همان لانه دارای 3 کبوتر است.
توجه دارید که در حالتهای زیادی از نشستن کبوترها در لانهها حداقل 1 لانه با حداقل 3 کبوتر میتواند وجود داشته باشد (همهٔ کبوترها در 1 لانه قرار بگیرند یا 5 کبوتر در 1 لانه و 4 کبوتر در لانهای دیگر یا ...).
مثال: در یک اردوی دانشآموزی حداقل چند دانشآموز وجود داشته باشند تا اطمینان داشته باشیم که حداقل 7 نفر از آنها ماه تولد یکسانی دارند؟
حل: در این مسئله $k+1=7$ یعنی $k=6$ است و n یا تعداد لانهها همان تعداد ماههای سال یعنی $n=12$ است، پس تعداد کبوترها یا معادل با آن تعداد دانشآموزان حداقل میبایست $kn+1=6\times 12+1=73$ باشد.
کار در کلاس (صفحهٔ 82 کتاب درسی)
1- در یک دبیرستان حداقل چند دانشآموز وجود داشته باشند تا مطمئن باشیم حداقل 10 نفر از آنها ماه و روز هفتهٔ تولدشان یکی است؟
2- 54 شاخه گل را حداکثر در چند گلدان قرار دهیم تا اطمینان داشته باشیم گلدانی هست که در آن حداقل 5 شاخه گل 2 قرار گرفته است؟
$k+1=....\Rightarrow k=....$
$kn+1=54\Rightarrow 4n=....\Rightarrow n=\left[ \frac{....}{4} \right]=....$
3- حداقل چند نفر در یک سالن همایش حضور داشته باشند تا مطمئن باشیم حداقل 3 نفر از آنها دو حرف اول و دوم فامیلشان غیر تکراری و مثل هم است؟ (فامیلیهایی مثل اشتری و اشراقی مورد نظر است).
مثال: حداقل چند نقطه از داخل مثلثی متساویالاضلاع به طول ضلع 2، انتخاب کنیم تا مطمئن باشیم حداقل 2 نقطه از آنها فاصلهشان کمتر از 1 است.
حل: کافی است مطابق شکل، مثلث مفروض را به 4 مثلث متساویالاضلاع به طول ضلع 1 تقسیمبندی کنید که در اینصورت اگر 5 نقطه از داخل این مثلث انتخاب کنید طبق اصل لانه کبوتری اطمینان دارید حداقل یکی از مثلثها شامل دست کم 2 نقطه از این 5 نقطه خواهد بود و فاصلهٔ این دو نقطه از طول ضلع مثلثهای کوچکتر کمتر میباشد.
مثال: نشان دهید در هر کلاس با n دانشآموز $(n\ge 2)$ حداقل 2 دانشآموز یافت میشوند که تعداد دوستان آنها در آن کلاس با هم برابر است.
حل: قبلاً ثابت کردیم که در هر گراف ساده حداقل 2 رأس هم درجه وجود دارد، لذا کافی است گرافی تعریف کنید که رأسهای آن دانشآموزان و رابطهٔ دوستی بین هر دو دانشآموز را با یالی بین رأسهای متناظرشان تعریف کنید.
تمرین (صفحهٔ 83 کتاب درسی)
1- در بین اعداد طبیعی 1 تا 90 $(1\le n\le 90)$ چند عدد وجود دارد که بر 2 یا 3 بخشپذیر باشند؟
2- در بین اعداد طبیعی 1 تا 200 $(1\le n\le 200)$ چند عدد و جود دارد که بر 4 بخشپذیر باشند ولی بر 7 بخشپذیر نباشند؟
3- در یک کلاس 34 نفری، 15 نفر فوتبال بازی میکنند، 11 نفر والیبال و 9 نفر بسکتبال بازی میکنند. اگر بدانیم 10 نفر عضو هیچیک از این سه تیم نبوده و 5 نفر فوتبال و والیبال، 6 نفر والیبال و بسکتبال و 3 نفر فوتبال و بسکتبال بازی میکنند مشخص کنید:
الف) چند نفر هر سه رشتهٔ ورزشی را بازی میکنند؟
ب) چند نفر فقط فوتبال بازی میکنند؟
پ) چند نفر والیبال بازی میکنند ولی بسکتبال بازی نمیکنند؟
ت) چند نفر فقط در یک رشته بازی میکنند؟
4- اگر بخواهیم یک قفل دارای رمز 5 رقمی و فاقد صفر را که سه رقم آن 7 و 2 و 3 هستند باز کنیم و تمام اعداد 5 رقمی را که شامل حداقل یک رقم 7 و یک رقم 2 و یک رقم 3 هستند در اختیار داریم و بستن و امتحان کردن هر یک از این اعداد 5 رقمی، 6 ثانیه طول بکشد، برای باز کردن این قفل حداکثر چقدر زمان نیاز داریم؟
5- چه تعداد تابع چون $f:A\to B$ میتوان تعریف کرد اگر بدانیم $\left| A \right|=5$ و $\left| B \right|=4$ است؟ چه تعداد از این توابع یکبهیک هستند؟
6- به چند طریق میتوان 5 کتاب مختلف را بین 8 نفر توزیع کرد، اگر بخواهیم به هر نفر حداکثر یک کتاب بدهیم؟
7- به چند طریق میتوان 6 فیلم سینمایی را بین سه داور برای داوری تقسیم کرد، بهطوریکه هر داور حداقل یک فیلم را داوری کند؟
8- ثابت کنید، در بین هر 368 نفر حداقل دو نفر هستند که در یک روز متولد شدهاند.
9- ثابت کنید، اگر در یک دبیرستان حداقل 505 دانشآموز مشغول تحصیل باشند لااقل 7 نفر از آنها روزِ هفته و ماه تولدشان یکسان است.
10- حداقل چند نفر در یک سالن ورزشی مشغول تماشای مسابقه کشتی باشند تا مطمئن باشیم لااقل 20 نفر از آنها روز تولدشان یکسان است؟
11- ثابت کنید در بین هر سه عدد طبیعی حداقل دو عدد طبیعی وجود دارد که مجموعشان عددی زوج باشد.
12- مجموعه اعداد $A=\left\{ 1,2,...,84 \right\}$ را در نظر میگیریم. نشان دهید هر زیرمجموعه 43 عضوی از A دارای حداقل 2 عضو است که مجموعهشان برابر با 85 باشد.
13- مجموعه اعداد $A=\left\{ 1,5,9,13,...,77,81,85 \right\}$ را که بهصورت یک تصاعد عددی مرتب شدهاند، در نظر میگیریم. اگر از این مجموعه 13 عضو انتخاب کنیم، نشان دهید که حداقل 2 عدد در این 13 عدد وجود دارد که مجموعشان برابر با 90 باشد.
14- 3 نقطه درون یک مستطیل $6\times 8$ قرار دارند. نشان دهید حداقل 2 نقطه از این 13 نقطه وجود دارد که فاصلهٔ آنها از هم، کمتر از $\sqrt{8}$ باشد.
15- 5 نقطه در صفحه با مختصات صحیح در نظر می گیریم. ثابت کنید حداقل دو نقطه از این 5 نقطه وجود دارد، طوریکه 15 مختصات نقطهٔ وسط این دو نقطه نیز صحیح میباشد.